public class Test03 {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums, 0, n - 1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        // 1. 根据中间元素将区间分成两部分
        int mid = (left + right) / 2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 计算翻转对，使用双指针来计算左边和右边的组合
        int cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid) {
            while (cur2 <= right && nums[cur1] > 2L * nums[cur2]) {
                cur2++;
            }
            ret += cur2 - (mid + 1);
            cur1++;
        }

        // 归并排序
        cur1 = left; cur2 = mid + 1;
        int i = left;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];

        // 将临时数组中的内容拷贝回原数组
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j];
        }
        return ret;
    }
}
